ハサミ将棋AI 思考アルゴリズム
1 状態空間の定義
1.1 状態 s
s = (B, T)
1.2 盤面
B(x,y) ∈ { 歩, と, ∅ }
各マスには「歩」「と」「空」のいずれかが存在する。
2. 行動集合と状態遷移
2.1 行動集合
行動sからとれる合法な手はA(s)として表現する。
行動集合A(s) = { (x,y) → (x',y') | すべて合法手 }
2.2 状態遷移関数
状態遷移関数をTとし、そこに現在の状態sと、合法手aを代入すると、次の状態s´になる。つまり、1手指したあとの状態。
s' = T(s, a)
3. 終端状態
terminal(s) =
{
true (駒数 ≤ 3)
false (それ以外)
}
どちらかの駒数が3以下になった時点でゲーム終了とする。
4. 木と分岐数
ゲームの進行は木として表現される。
5.1 分岐数
平均分岐数bを以下のように見積もる
b ≒ 駒数 × 平均移動数 ≒ 9 × 10 = 90
5. ミニマックス法
5.1 価値関数 V(s)
今回の評価基準は
1. 端を避ける
2. 動けやすい
3. 危険を回避
4. 駒の数が多い
V(s) =
{
Eval(s) (終端 or 深さ0)
maxₐ V(T(s,a)) (CPU手番)
minₐ V(T(s,a)) (人手番)
}
CPUは常に「最悪の場合でも最大の結果」を選択する。
6. 評価関数 Eval(s)
6.1 線形評価モデル
Eval(s) = Σ wᵢ fᵢ(s)
7.2 特徴量
| 特徴 | 数式 |
|---|
| 駒差 | #to − #hu |
| 中央支配 | Σ c(p) |
| 可動性 | 合法手数差 |
7.3 重み例
Eval(s) = 100·f₁ + 5·f₂ + 2·f₃
8. αβ枝刈り
探索中、以下が成立した時点で探索を中断する。
α ≥ β ⇒ 枝刈り
これにより計算量は理論上、
O(b^d) → O(b^(d/2))
まで削減される。
9. 反復深化探索
深さを1から順に増やして探索する。
depth = 1
while(時間が残っている){
探索(depth)
depth++
}
時間切れでも、最後に完全探索できた結果が必ず残る。
10. 停止保証
探索開始時刻 t₀ と現在時刻 t を比較する。
t − t₀ > 制限時間 ⇒ 即終了
これによりフリーズは理論上起こり得ない。
11. 人間の思考との対応
| 人間の感覚 | 数理的意味 |
|---|
| 危ない | min値が低い |
| 囲まれる | 可動性低下 |
| 中央が強い | f₂増大 |
| 一気に取られる | f₁急減 |
12. 総括
このAIは、有限零和完全情報ゲームに対し、
argmaxₐ ( min 相手返し ( Eval(s) ) )
を、時間制限下で最適に近似するアルゴリズムである。
これは「思考しているように見える」のではなく、
数学的に正しく思考していることを意味する。